Homework 2¶

INSERT YOUR NAME HERE

Directions: Add work to this notebook to solve the problems below.

Be careful to name the objects you create as described in the problem. Some problems may include some tests you can run to test your code.

You must do exact arithemetic unless a problem suggests otherwise!

References: Some problems are derived from problems in the book:

  • CM: Computational Mathematics with SageMath by Paul Zimmermann, Alexandre Casamayou, Nathann Cohen, Guillaume Connan, Thierry Dumont, Laurent Fousse, François Maltey, Matthias Meulien, Marc Mezzarobba, Clément Pernet, Nicolas M. Thiéry, Erik Bray, John Cremona, Marcelo Forets, Alexandru Ghitza, and Hugh Thomas. (freely available for download)

1. Triangle construction in the complex plane¶

Multiplication by the complex number $w = \frac{1+i}{2}$ rotates the plane by $\frac{\pi}{4}$ and scales the plane by $\frac{\sqrt{2}}{2}$, as shown below:

In [1]:
w = (1 + I) / 2
arg(w)
Out[1]:
1/4*pi
In [2]:
abs(w)
Out[2]:
sqrt(1/2)

It follows that for any pair of complex numbers $a, b \in {\mathbb C}$, these two points together with the point $$c = a + w (b-a)$$ form a 45-45-90 triangle $\triangle abc$ in the complex plane with hypotenuse $\overline{ab}$. Write a Python function other_vertex(a, b), which given a and b, returns c.

In [ ]:

Tests for your code:

This checks if other_vertex is defined:

In [ ]:
try:
    other_vertex
except NameError:
    print('There must be an error: the variable other_vertex is not defined!')

This checks that other_vertex is a function:

In [ ]:
if not callable(other_vertex):
    print('There must be an error: other_vertex is not a Python function')

This checks the case a=0 and b=1.

In [ ]:
if other_vertex(0, 1) != (1+I)/2:
    print('The value returned by `other_vertex(0, 1)` is incorrect.')

Here we check a=1 and b=2+I:

In [ ]:
if other_vertex(1, 2+I) != 1+I:
    print('The value returned by `other_vertex(0, 1)` is incorrect.')

Here we give a visual check for some more strange points:

In [ ]:
a = 2/3 + I
b = -1 + I/2
c = other_vertex(a, b)
line2d([a, b, c, a], color='red', aspect_ratio=1)

2. Point list evolution¶

This problem builds on the previous one where you defined other_vertex. Write a Python function add_points which takes as input a list of complex numbers, $$[a_0, a_1, \ldots, a_{l-1}] \quad \text{where $l$ is the length of the list}.$$ The function should return a new list that includes each $a_i$, but also includes $\textrm{other_vertex}(a_i, a_{i+1})$ between any two consecutive elements of the list $a_i$ and $a_{i+1}$. The returned list should have length $2l-1$ and be of the following form: $$[a_0, b_0, a_1, b_1, \ldots, a_{l-2} , b_{l-2}, a_{l-1}],$$ where $b_i = \textrm{other_vertex}(a_i, a_{i+1}).$

In [ ]:

Tests for your code:

This checks if add_points is defined:

In [ ]:
try:
    add_points
except NameError:
    print('There must be an error: the variable add_points is not defined!')

This checks if add_points is a function.

In [ ]:
if not callable(add_points):
    print('There must be an error: add_points is not a Python function')

If the function is passed the list $[0, 1]$, then the list $\left[0, \frac{1+I}{2}, 1\right]$ should be returned. We'll plot the returned list using line2d and check the answer. If no messages are printed then your function worked in this case.

In [ ]:
new_list = add_points([0, 1])
if type(new_list) != list:
    print('There is an error: add_points should return a list.')
if tuple(new_list) != (0, (1+I)/2, 1):
    print('There is an error: the list returned by add_points([0, 1]) is incorrect.')
show(line2d(new_list, aspect_ratio=1))

Now we'll apply add_points to [0, I, 1].

In [ ]:
new_list2 = add_points([0, I, 1])
if type(new_list2) != list:
    print('There is an error: add_points should return a list.')
if tuple(new_list2) != (0, (I-1)/2, I, 1+I, 1):
    print('There is an error: the list returned by add_points([new_list]) is incorrect.')
show(line2d(new_list2, aspect_ratio=1))

3. Iteration and fractal construction¶

Given a function $f:X \to X$, the $n$-fold composition of $f$ with itself, $f^{\circ n}$ is also a function $X \to X$ and is defined by $$f^{\circ n} = \underbrace{f\circ f \circ \ldots \circ f}_{\text{$n$ copies}}.$$

Write a Python function iterate which takes as input a Python function f, a positive natural number n, and an element $x$ from the domain of f. The function should return $f^{\circ n}(x)$.

In [ ]:

Tests for your code:

For example, if $f(x)=2x$, then iterate(f, 2, 3) should return $12$.

In [ ]:
f(x) = 2*x
if iterate(f, 2, 3) == 12:
    print('Good job, we got 12!')
else:
    print('The output of iterate(f, 2, 3) is incorrect!')

Consider the function $$f(x)=x+\frac{1}{2x}.$$ Experimentally, it seems to be true that for any $x>0$, we have $$\lim_{n \to \infty} |f^{\circ n}(x)-\sqrt{n}| = 0.$$ That is, $f^{\circ n}(x)$ gets closer and closer to $\sqrt{n}$. (I'm not sure why this is true. Can anyone prove it?)

In [ ]:
f(x) = x + 1/(2*x)
value = iterate(f, 100, 1.0) # Use floating point arithmetic for large iteration!
print(f'You computed f^100(1.0) = {value}.')
if abs(value-10.111) > 10^-4:
    print('The computed value is wrong.')
else:
    print('The computed value is correct.')

We can also iterate our function add_points.

In [ ]:
l = [0, 1]
fractal = iterate(add_points, 10, l)
line2d(fractal, aspect_ratio=1)

Keep in mind there will be about $2^n$ points in the list obtained by iterate(add_points, n, [0, 1]). We have $2^10=1024$ and so $2^{20}$ is already over a million points. We probably don't want to compute with more than $n=15$ or so.

In [ ]:
l = [0, 1]
fractal = iterate(add_points, 14, l)
line2d(fractal, aspect_ratio=1, axes=False)

Here are a couple more examples:

In [ ]:
fractal = iterate(add_points, 13, [0, 1, 1+I, I, 0])
line2d(fractal, aspect_ratio=1, axes=False)
In [ ]:
fractal = iterate(add_points, 13, [0, I, 1+I, 1, 0])
line2d(fractal, aspect_ratio=1, axes=False)

4. Other fractals¶

Vary the construction above to draw other examples of fractals (or other objects).

One simple way to to this would be to replace the roll of $w = \frac{1+i}{2}$ by another number. When constructing $\triangle abc$, it is important that the length of $\overline{ac}$ and $\overline{bc}$ be shorter than that of $\overline{ab}$. Here I am still assuming you define $c = a + w(b-a)$ (though of course you could try other things). This translates to the condition that $|w|<1$ and $|w-1|<1$.

Another possibility would be to choose multiple values of $w$. If you choose two values $w_1$ and $w_2$, then you could edit a list by inserting both $a + w_1(b-a)$ and $a+w_2(b-a)$ between two consecutive values $a$ and $b$.

In [ ]: